#!/usr/bin/env python2
# -*- coding: utf-8 -*-

"""
HW: старое задание - написать ф-ю, возвр regexp (было - dfa), кот. оп. ч. кратн. n

def re_multiple(n):
    ...
    return r

r = re_multiple(2)
if re.search(r, '100'): # not '101' or '0100'
    print 'yes'
"""

import random
import re


def dfa_multiples(n):
    """
    Takes integer n and constructs a dfa that matches any mutiple of n in binary
    """
    d = [{} for i in range(n + 3)]
    d[n]['0'] = n + 1
    d[n]['1'] = 1
    d[n + 1]['0'] = n + 1
    d[n + 1]['1'] = n + 2
    d[n + 2]['0'] = n + 2
    d[n + 2]['1'] = n + 2
    for i in range(n):
        for c in ['0', '1']:
            d[i][c] = (i * 2 + int(c, 2)) % n # magic happens here
    return d

def multiples(n):
    # Your code here
    pass


def test_multiples(n, t=1000, u=1000):
    r = multiples(n)
    for i in range(t + 1):
        if not test_binary_string(bin(i)[2:], r, n):
            return False
    print 'Successfully checked all numbers up to', t

    for i in range(u):
        s = ''.join(random.choice('01') for j in range(random.randint(0, 63)))
        if not test_binary_string(s, r, n):
            return False
    print 'Successfully checked', u, 'random binary strings'
    return True


def test_binary_string(s, r, n):
    match = re.search(r, s)
    if s == '':
        if match:
            print 'Error: the regular expression for', n, 'matches the empty string'
            return False
    elif s[0] != '1' and len(s) > 1:
        if match:
            print 'Error: the regular expression for', n, 'matches', s
            return False
    else:
        i = int(s, 2)
        if match:
            if i % n > 0:
                print 'Error: the regular expression for', n, 'matches', i
                return False
        elif i % n == 0:
            print 'Error: the regular expression for', n, 'does not match', i
            return False
    return True

if __name__ == '__main__':
    for n in [2, 3, 4, 5, 7, 11, 12]:
        T = dfa_multiples(n)
        print "n=%d:" % (n,)
        for i in range(len(T)):
            print '{0:4d}  {1}'.format(i, T[i])
        print
